import java.util.Arrays;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 */
public class Solution_34 {
    /**
     * 方法二：二分查找
     * <p>
     * 「第一个 <b>大于等于</b> target 的数字的下标」记作 leftIndex 和 
     * 「第一个 <b>大于</b> target 的数字的下标减1」记作 rightIndex
     * <p>
     * 时间复杂度：O(logN)
     * 空间复杂度：O(1)
     */
    public int[] searchRange(int[] nums, int target) {
        int[] ans = { -1, -1 };
        int leftIndex = binarySearch(nums, target, true);
        int rightIndex = binarySearch(nums, target, false) - 1;
        if (leftIndex <= rightIndex && rightIndex < nums.length 
                && nums[leftIndex] == target && nums[rightIndex] == target) {
            ans[0] = leftIndex;
            ans[1] = rightIndex;
        }
        return ans;
    }

    /**
     * 在 nums 数组中二分查找 target 的位置 
     * 如果 lower 为 true，则查找第一个大于等于 target 的下标， 
     * 否则查找第一个大于 target 的下标
     */
    private int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    /**
     * 方法一：线性扫描
     * <p>
     * 时间复杂度：O(N) 
     * 空间复杂度：O(1)
     */
    public int[] searchRange1(int[] nums, int target) {
        int[] ans = { -1, -1 };

        int len = nums.length;
        if (len == 0) {
            return ans;
        }

        int i = 0;
        while (i < len && nums[i] != target) {
            i++;
        }
        if (i == len) {
            return ans;
        }
        ans[0] = i;
        while (i < len && nums[i] == target) {
            i++;
        }
        ans[1] = i - 1;
        return ans;
    }

    public static void main(String[] args) {
        Solution_34 solution = new Solution_34();
        int[] nums = { 5, 7, 7, 8, 8, 10 };
        int target = 6;
        int[] ans = solution.searchRange(nums, target);
        System.out.println(Arrays.toString(ans));
    }
}
